/**
 * @file caculator.h
 * @author 张奕欣 (3190105655@zju.edu.cn)
 * @brief 
 * @version 0.1
 * @date 2022-12-24
 * 
 * @copyright Copyright (c) 2022
 * 
 */
#include <stack>
#include <vector>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;

vector<string> postfix;				//后缀表达式向量
stack<char> opStack;				//符号栈
stack<double> numStack;				//数字栈
string stdInfix;					//自定义标准格式化表达式
double result;						//最终计算结果
	
//获取算术符号优先级
int prior(char c) {
	if (c == '+' || c == '-') 
	{
		return 1;
	}
	if (c == '*' || c == '/') 
	{
		return 2;
	}
	if (c == '^') 
	{
		return 3;
	}
	return 0;
}

//后缀表达式转换
void getPostfix() 
{

	string tmp;

	for (size_t i = 0; i < stdInfix.length(); i++) 
	//string.size()返回size_type类型，避免下标运算时的类型溢出。比int 类型要好
    {					
		tmp = "";
		switch (stdInfix[i]) 
        {
			/**
			 * @brief 讨论运算符号的情形
			 * 
			 */
		    case '+':
    		case '-':
	    	case '*':
		    case '/':
	    	case '^':
			//以上操作符均进行下面的操作
				if (opStack.empty() || opStack.top() == '('  )
				//栈空或者是左括号直接入栈
    	        {
					opStack.push(stdInfix[i]);
				}
				else
				//更高优先级或者相同优先级的运算入栈后，该运算符入栈 
				{
					while (!opStack.empty() && (prior(opStack.top()) >= prior(stdInfix[i]))) 
					{
						tmp += opStack.top();
						postfix.push_back(tmp);
						opStack.pop();
						tmp = "";
					}
					opStack.push(stdInfix[i]);
				}
				break;

    		case '(':
				opStack.push(stdInfix[i]);
				break;
	    	case ')':
		    	while (!opStack.empty() && opStack.top() != '(') 
                {
			    	tmp += opStack.top();
				    postfix.push_back(tmp);
				    opStack.pop();
				    tmp = "";
			    }
			    if (!opStack.empty() && opStack.top() == '(') 
                {
					opStack.pop(); //将左括号出栈丢弃
			    }
				//没有匹配上左括号说明表达式有问题
				if (opStack.empty())
				{
					cout << "Error: Bracket not match!" << endl;
					exit(1);
				}
			    break;

			/**
			 * @brief 讨论运算数
			 * 
			 */
		    default:
			    if ((stdInfix[i] >= '0' && stdInfix[i] <= '9')) 
                {
				    tmp += stdInfix[i];
			    	while (i + 1 < stdInfix.length() && 
						(stdInfix[i + 1] >= '0' && stdInfix[i + 1] <= '9' || 
						stdInfix[i + 1] == '.')) 
                    {		
						//浮点数处理
				    	tmp += stdInfix[i + 1];			
                        //是连续的数字，则追加
				    	i++;
				    }

    				if (tmp[tmp.length() - 1] == '.') 
                    {
		    			tmp += '0';						
                        //将x.做x.0处理
				    }
	    			postfix.push_back(tmp);
		    	}
			    break;
		}//end switch
	}//end for

	//将栈中剩余符号加入后缀表达式
	while(!opStack.empty()) 
    {					
		tmp = opStack.top();
		postfix.push_back(tmp);
		opStack.pop();
	}
}



/**
 * @brief 表达式自定义标准格式化，并且将中缀表达式转化为后缀表达式
 * 
 */
void calculator(string infix) 
{

	stdInfix = infix;

	//实现正负数
	for (size_t i = 0; i < stdInfix.size(); i++) 
    {			
        //string.size()返回size_type类型，避免下标运算时的类型溢出
		if (stdInfix[i] == '-' || stdInfix[i] == '+') 
        {		
            //-x转换为0-x，+x转化为0+x
			if (i == 0) 
			{
				stdInfix.insert(0, 1, '0');
			}
			else if (stdInfix[i - 1] == '(') 
			{
				stdInfix.insert(i, 1, '0');
			}
		}
	}
	getPostfix(); //将中缀表达式转化为后缀表达式
}



/**
 * @brief 将数字和符号匹配计算
 * 
 * @param op1 
 * @param op2 
 * @param numStack 
 */
void opcal(double &op1, double &op2, stack<double> &numStack)
{
	if (!numStack.empty()) 
	{
		op2 = numStack.top();
		numStack.pop();
		op1 = numStack.top();
		numStack.pop();
	}
}

/**
 * @brief 计算后缀表达式
 * 
 */
void calPostfix() 
{

	string tmp;
	double number = 0;
	double op1 = 0;
	double op2 =0;

	for (size_t i = 0; i < postfix.size(); i++) 
	{
		tmp = postfix[i];
		if (tmp[0] >= '0' && tmp[0] <= '9') 
		{
			number = atof(tmp.c_str());
			numStack.push(number);
		}
		else if (postfix[i] == "+") 
		{
			opcal(op1,op2,numStack);
			numStack.push(op1 + op2);
		}
		else if (postfix[i] == "-") 
		{
			opcal(op1,op2,numStack);
			numStack.push(op1 - op2);
		}
		else if (postfix[i] == "*") 
		{
			opcal(op1,op2,numStack);
			numStack.push(op1* op2);
		}
		else if (postfix[i] == "/") 
		{
			opcal(op1,op2,numStack);
			if (op2 == 0) 
			{
				cout << "Error: Divide by 0!" <<endl;
				exit(1);
			}
			numStack.push(op1 / op2);
		}
		else if (postfix[i] == "^") 
		{
			opcal(op1,op2,numStack);
			numStack.push(pow(op1, op2));
		}
	}//end for
	if (!numStack.empty()) 
	{
		result = numStack.top();
	}
	else 
	{
		cout << "Error: Operators and figures not match!" << endl;
		exit(1);
	}
}


double getResult(string infix) 
{
    calculator(infix);
	calPostfix();				//获取算术结果
	return result;
}
